package com.my.algorithmlearning.leetcode;

import org.apache.commons.lang3.StringUtils;
import org.springframework.util.Assert;

/**
 * @ClassName CountBits
 * @Description CountBits
 * @Author wanghaiwei
 * @Date 2023/1/17 10:08
 */
public class CountBits {
    public int[] countBitsDoubleLoop(int n) {
        int[] results = new int[n+1];
        for (int i = 0; i <= n; i++) {
            int countBits = 0;
            int remainder = 0;
            int divisor = i;
            do{
                remainder = divisor % 2;
                divisor = divisor / 2;
                if (remainder == 1) {
                    countBits++;
                }
            }while(divisor != 0);
            results[i] = countBits;
        }
        return results;
    }
    public int[] countBitsByDeductTail(int n) {
        int[] results = new int[n+1];
        for (int i = 0; i <= n; i++) {
            int countBits = 0;
            int num = i;
            while(num != 0) {
                num = num & (num - 1);
                countBits++;
            }
            results[i] = countBits;
        }
        return results;
    }

    public int[] countBitByDynamic(int n) {
        int[] results = new int[n+1];
        results[0] = 0;
        for (int i = 0; i <=n; i++) {
            if (i % 2 == 1) {
                results[i] = results[i-1] + 1;
            }else {
                results[i] = results[i/2];
            }
        }
        return results;
    }

    public static void main(String[] args) {
        CountBits solution = new CountBits();
        String result = StringUtils.join(solution.countBitsDoubleLoop(2), ',');
        Assert.isTrue("0,1,1".equals(result), "countBitsDoubleLoop:n=2计算错误:预期0,1,1，实际" + result);
        result = StringUtils.join(solution.countBitsDoubleLoop(5), ',');
        Assert.isTrue("0,1,1,2,1,2".equals(result), "countBitsDoubleLoop:n=5计算错误:预期0,1,1,2,1,2，实际" + result);

        result = StringUtils.join(solution.countBitsByDeductTail(2), ',');
        Assert.isTrue("0,1,1".equals(result), "countBitsByDeductTail:n=2计算错误:预期0,1,1，实际" + result);
        result = StringUtils.join(solution.countBitsByDeductTail(5), ',');
        Assert.isTrue("0,1,1,2,1,2".equals(result), "countBitsByDeductTail:n=5计算错误:预期0,1,1,2,1,2，实际" + result);

        result = StringUtils.join(solution.countBitByDynamic(2), ',');
        Assert.isTrue("0,1,1".equals(result), "countBitByDynamic:n=2计算错误:预期0,1,1，实际" + result);
        result = StringUtils.join(solution.countBitByDynamic(5), ',');
        Assert.isTrue("0,1,1,2,1,2".equals(result), "countBitByDynamic:n=5计算错误:预期0,1,1,2,1,2，实际" + result);
    }
}
